package offer;

import java.util.ArrayList;
import java.util.List;

public class offerII_0062 {
    class Trie {
        boolean next;
        boolean empty;
        boolean end;
        List<Trie> list;
        /** Initialize your data structure here. */
        public Trie() {
            next=false;
            empty=true;
            end=false;
            list=new ArrayList<>(26);
            for(int i=0;i<26;++i){
                list.add(null);
            }
        }

        /** Inserts a word into the trie. */
        public void insert(String word) {
            int len=word.length();
            if(this.next!=true) {
                for(int i=0;i<26;++i){
                    list.set(i,new Trie());
                }
            }
            this.next=true;
            Trie tmp=this;
            for(int i=0;i<len;++i){
                tmp=tmp.list.get(word.charAt(i)-'a');
                if(tmp.next!=true) {
                    for(int j=0;j<26;++j){
                        tmp.list.set(j,new Trie());
                    }
                }
                tmp.empty=false;
                if(i!=len-1) tmp.next=true;
                if(i==len-1) tmp.end=true;
            }
        }

        /** Returns if the word is in the trie. */
        public boolean search(String word) {
            int len=word.length();
            Trie tmp=this;
            for(int i=0;i<len;++i){
                if(i!=len-1&&tmp.next==false) return false;
                tmp=tmp.list.get(word.charAt(i)-'a');
                if(tmp==null||tmp.empty==true) return false;
                if(i==len-1&&tmp.end==false) return false;
            }
            return true;
        }

        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
            int len=prefix.length();
            Trie tmp=this;
            for(int i=0;i<len;++i){
                if(i!=len-1&&tmp.next==false) return false;
                tmp=tmp.list.get(prefix.charAt(i)-'a');
                if(tmp==null||tmp.empty==true) return false;
            }
            return true;
        }
    }
}
